Task #1124

Memory 32 MB Time 1000 ms Complexity 18 %

#Prefix Sum

#Suffix Array

#Two Pointers

#Tartiblash

Maximum sum

Sizga uzunligi \(N\) ga teng bo'lgan \(a_1, a_2, a_3, ..., a_N\) massiv berilgan. Siz bu massiv ustida \(K\) ta amal bajarishingiz kerak. Natijada hosil bo'lgan massiv summasi maximal bo'lib qolsin.

bitta amal bilan siz massivdagi eng kichik 2ta elementni o'chirishingiz mumkin.
bitta amal bilan massivdagi eng katta 1ta elementni o'chirishingiz mumkin.

Eslatma: amallani o'zingiz tanlaysiz.

Input:

Kirish faylining birinchi qatorida ikkita butun son \(N,K\)\((3\le N \le 2*10^5; 1\le K \le 99999 ; 2K \le N-1)\)kiritiladi.
Ikkinchi qatorda \(a_i\)\((1\le a_i \le 10^9)\) massiv elementlari kiritiladi.

Output:

Chiqish faylida \(K\) ta amal bajarilgandan keyingi massivning maximal summasini chiqaring.

Examples

#	input.txt	output.txt
1	5 1 2 5 1 10 6	21
2	5 2 2 5 1 10 6	11
3	6 1 15 22 12 10 13 11	62
4	6 2 15 22 12 10 13 11	46

Telegram Facebook

Submit answer

Please, sing in, to complete this action, if you don't have account, you can sign up any moment